package code.starivan.leetcode;

/**
 * Created by Ivan on 2015/8/22.
 */

//There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
public class N004_MedianOfTwo {


    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1=nums1.length,length2=nums2.length;
        int totalLengh=length1+length2;
        if((totalLengh%2)==1){
            return findKth(nums1,0,length1,nums2,0,length2,totalLengh/2+1);
        }else{
            return (findKth(nums1,0,length1,nums2,0,length2,totalLengh/2)+
                    findKth(nums1,0,length1,nums2,0,length2,totalLengh/2+1))/2.0;
        }
    }

    public double findKth(int[] num1, int startIndex1, int length1,
                          int[] num2, int startIndex2, int length2,
                          int k) {
        if (length1 > length2)
            return findKth(num2, startIndex2, length2, num1, startIndex1, length1, k);

        if(length1==0)
            return num2[startIndex2+k-1];

        if(k==1)
            return Math.min(num1[startIndex1],num2[startIndex2]);

        int pa = Math.min(k / 2, length1);
        int pb = k - pa;

        int value1 = num1[startIndex1 + pa - 1];
        int value2 = num2[startIndex2 + pb - 1];
        if (value1 < value2) {
            return findKth(num1, startIndex1 + pa, length1 - pa, num2, startIndex2, length2, k - pa);
        } else if (value1 > value2) {
            return findKth(num1, startIndex1, length1, num2, startIndex2 + pb, length2 - pb, k - pb);
        } else {
            return value1;
        }
    }

}
